翻訳と辞書 Words near each other ・ K-Commando ・ K-Commerce ・ K-complex ・ K-convex function ・ K-d tree ・ K-D-B-tree ・ K-Day ・ K-Days ・ K-Dee ・ K-Def ・ K-Developedia ・ K-distribution ・ K-Dow Petrochemicals ・ K-Drama (rapper) ・ K-edge ・ K-edge-connected graph ・ K-Electric ・ K-Electric F.C. ・ K-epsilon turbulence model ・ K-equivalence ・ K-factor ・ K-factor (actuarial) ・ K-factor (aeronautics) ・ K-factor (Cisco) ・ K-factor (fire protection) ・ K-factor (marketing) ・ K-factor (telecommunications) ・ K-finite ・ K-frame ・ K-function Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク K-edge-connected graph ： ウィキペディア英語版 K-edge-connected graph In graph theory, a connected graph is ''k''-edge-connected if it remains connected whenever fewer than ''k'' edges are removed. The edge-connectivity of a graph is the largest ''k'' for which the graph is ''k''-edge-connected. ==Formal definition== Let $G\; =\; (V,\; E)$ be an arbitrary graph. If subgraph $G\text{'}\; =\; (V,\; E\; \backslash setminus\; X)$ is connected for all $X\; \backslash subseteq\; E$ where , then ''G'' is ''k''-edge-connected. The edge connectivity of $G$ is the maximum value ''k'' such that ''G'' is ''k''-edge-connected. The smallest set ''X'' whose removal disconnects ''G'' is a minimum cut in ''G''. The edge connectivity version of Menger's theorem provides an alternative and equivalent characterization, in terms of edge-disjoint paths in the graph. If every two vertices of ''G'' form the endpoints of ''k'' paths, no two of which share an edge with each other, then ''G'' is ''k''-edge-connected. In one direction this is easy: if a system of paths like this exists, then every set ''X'' of fewer than ''k'' edges is disjoint from at least one of the paths, and the pair of vertices remains connected to each other even after ''X'' is deleted. In the other direction, the existence of a system of paths for each pair of vertices in a graph that cannot be disconnected by the removal of few edges can be proven using the max-flow min-cut theorem from the theory of network flows. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「K-edge-connected graph」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.